package com.c2b.algorithm.leetcode.base.backtracking;

/**
 * <a href='https://leetcode.cn/problems/word-search/description/'>单词搜索(Word Search)</a>
 * <p>给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。</p>
 * <p>单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：board =
 *          [[<a color='blue'>'A'</a>,<a color='blue'>'B'</a>,<a color='blue'>'C'</a>,'E'],
 *           ['S','F',<a color='blue'>'C'</a>,'S'],
 *           ['A',<a color='blue'>'D'</a>,<a color='blue'>'E'</a>,'E']
 *           ],
 *           word = 'ABCCED'
 *      输出：true
 *
 * 示例 2：
 *      输入：board =
 *          [['A','B','C','E'],
 *           ['S','F','C',<a color='blue'>'S'</a>],
 *           ['A','D',<a color='blue'>'E'</a>,<a color='blue'>'E'</a>]
 *           ],
 *           word = 'SEE'
 *      输出：true
 *
 * 示例 3：
 *      输入：board =
 *          [['A','B','C','E'],
 *           ['S','F','C','S'],
 *           ['A','D','E','E']
 *          ],
 *          word = 'ABCB'
 *      输出：false
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>m == board.length</li>
 *         <li>n = board[i].length</li>
 *         <li>1 <= m, n <= 6</li>
 *         <li>1 <= word.length <= 15</li>
 *         <li>board 和 word 仅由大小写英文字母组成</li>
 *     </ul>
 * </p>
 *
 * <b>进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？</b>
 *
 * @author c2b
 * @since 2023/10/27 13:36
 */
public class LC0079WordSearch_M {

    static class Solution {
        public boolean exist(char[][] board, String word) {
            boolean[][] used = new boolean[board.length][board[0].length];
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[0].length; j++) {
                    if (dfs(board, used, i, j, 0, word)) {
                        return true;
                    }
                }
            }
            return false;
        }

        private boolean dfs(char[][] board, boolean[][] used, int currRow, int currCol, int currIndex, String word) {
            // 如果越界 或者当前字符被使用过
            if (currRow < 0 || currRow > board.length - 1 || currCol < 0 || currCol > board[0].length - 1 || currIndex >= word.length()) {
                return false;
            }
            // 如果当前位置的字符已经被使用过
            if (used[currRow][currCol]) {
                return false;
            }
            char currChar = board[currRow][currCol];
            // 如果当前位置的字符 与 word对应位置的字符不匹配
            if (currChar != word.charAt(currIndex)) {
                return false;
            } else if (currIndex == word.length() - 1) {
                // 如果当前位置的字符 与 word对应位置的字符匹配,并且已经到了word的最后一个单词
                return true;
            }
            used[currRow][currCol] = true;
            //// 上、下、左、右。任意方向有满足的答案，均可返回
            //if (dfs(board, used, currRow - 1, currCol, currIndex + 1, word)) {
            //    return true;
            //}
            //if (dfs(board, used, currRow + 1, currCol, currIndex + 1, word)) {
            //    return true;
            //}
            //if (dfs(board, used, currRow, currCol - 1, currIndex + 1, word)) {
            //    return true;
            //}
            //if (dfs(board, used, currRow, currCol + 1, currIndex + 1, word)) {
            //    return true;
            //}
            //used[currRow][currCol] = false;
            //return false;
            int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
            for (int[] direction : directions) {
                if (dfs(board, used, currRow + direction[0], currCol + direction[1], currIndex + 1, word)) {
                    return true;
                }
            }
            used[currRow][currCol] = false;
            return false;
        }
    }

    public static void main(String[] args) {
        char[][] board = {
                {'A', 'B', 'C', 'E'},
                {'S', 'F', 'C', 'S'},
                {'A', 'D', 'E', 'E'}
        };
        Solution solution = new Solution();
        //System.out.println(solution.exist(board, "ABCCED"));
        char[][] board2 = {
                {'E', 'B', 'C', 'E'},
                {'S', 'F', 'C', 'S'},
                {'E', 'D', 'E', 'E'}
        };
        System.out.println(solution.exist(board2, "SEE"));
        //System.out.println(solution.exist(board, "ABCB"));

    }
}
